#include <iostream>
#include "BSTNode.h"
using namespace std;

BSTNode* lowest_common_ancestor_BST(BSTNode *root, BSTNode *a, BSTNode *b){
	if(!root||!a||!b) return NULL;

	if(a->data < root->data && b->data < root->data){
		return lowest_common_ancestor_BST(root->left, a, b);
	}else if(a->data > root->data && b->data > root->data){
		return lowest_common_ancestor_BST(root->right, a, b);
	}else
	{
		//if a== root or b== root, or a and b split
		return root;
	}
}

BSTNode* lowest_common_ancestor_BST_Iterative(BSTNode *root, BSTNode *a, BSTNode *b){
	if(!root||!a||!b) return NULL;

	BSTNode *cur=root;

	while(cur!=NULL){
		if(a->data<cur->data&&b->data<cur->data)
			cur=cur->left;
		else if(a->data>cur->data&&b->data>cur->data)
			cur=cur->right;
		else
			break;
	}
	return cur;
}

/*for a BT*/
int matchPQ(BSTNode *root, BSTNode *p, BSTNode *q){
	if(!root) return 0;
	int matches = matchPQ(root->left, p, q)+matchPQ(root->right, p, q);
	if(root==p||root==q)
		return matches+1;
	else return matches;
}


BSTNode *lowest_common_ancestor_BT(BSTNode *root, BSTNode *p, BSTNode *q){
	if(!root||!p||!q) return NULL;
	if(root==p||root==q) return root;
	int totalMatches = matchPQ(root->left, p, q);
	if(totalMatches == 1)
		return root;
	else if (totalMatches == 2)
		return lowest_common_ancestor_BT(root->left, p, q);
	else
		return lowest_common_ancestor_BT(root->right, p, q);
}
